﻿// 607 最小点数负环.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
http://oj.daimayuan.top/course/22/problem/993

给定一张 n个顶点 m 条边的带权有向简单图，顶点编号从 1 到 n
，请找出一个顶点数最小的环，使得环上的边权和为负数。

输入格式
第一行两个整数 n,m，表示顶点数和边数。

接下来 m 行，每行三个整数 u,v,w
，表示 u 号点到 v 号点有一条边权为 w 的边。

输出格式
输出一行一个整数表示顶点数最小的负环上的顶点数，如果不存在负环输出 -1。

样例输入
3 6
1 2 -2
2 1 1
2 3 -10
3 2 10
3 1 -10
1 3 10
样例输出
2
数据规模
对于 100% 的数据，保证 1≤n≤300,0≤m≤n(n−1),1≤u,v≤n,−104≤w≤104。
*/


#include <iostream>
#include <cstring>

using namespace std;

int  n, m, f[10][310][310];
int v[310][310], g[310][310];



int main()
{
	cin >> n >> m;
	memset(f, 0x3f, sizeof f);
	for (int i = 1; i <= n; i++)
		f[0][i][i] = 0;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		f[0][x][y] = z;
	}
	for (int i = 1; i <= 9; i++)
		for (int x = 1; x <= n; x++)
			for (int y = 1; y <= n; y++)
				for (int z = 1; z <= n; z++)
					if (f[i - 1][x][z]< 0x3f3f3f3f  && f[i-1][z][y] < 0x3f3f3f3f)
						f[i][x][y] = min(f[i][x][y], f[i - 1][x][z] + f[i - 1][z][y]);

	int ans = 0;
	memset(v, 0x3f, sizeof  v);
	for (int i = 1; i <= n; i++)
		v[i][i] = 0;
	for (int i = 9; i >= 0; --i) {
		memset(g, 0x3f, sizeof g);
		for (int x = 1; x <= n; x++)
			for (int y = 1; y <= n; y++)
				for (int z = 1; z <= n; z++)
					if (v[x][z] < 0x3f3f3f3f && f[i][z][y] < 0x3f3f3f3f)
						g[x][y] = min(g[x][y], v[x][z] + f[i][z][y]);

		bool ok = true;
		for (int j = 1; j <= n&&ok; j++)
			if (g[j][j] < 0)
				ok = false;
		if (ok) {
			ans += (1 << i);
			memcpy(v, g, sizeof v);
		}
	}
	++ans;
	if (ans > n)
		cout << -1 << endl;
	else
		cout << ans << endl;


	return 0;
}

 